package org.aplombh.java.awcing.basic.dp.linearDP;

import java.io.*;

/**
 * 给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
 * <p>
 * 输入格式
 * 第一行包含整数 N。
 * <p>
 * 第二行包含 N 个整数，表示完整序列。
 * <p>
 * 输出格式
 * 输出一个整数，表示最大长度。
 * <p>
 * 数据范围
 * 1≤N≤1000，
 * −109≤数列中的数≤109
 * 输入样例：
 * 7
 * 3 1 2 1 8 5 6
 * 输出样例：
 * 4
 */
public class LongestAscendingSubsequence_896 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());
        LAS2 las = new LAS2(n);
        String[] str = reader.readLine().split(" ");
        for (int j = 1; j <= n; j++) {
            las.a[j] = Integer.parseInt(str[j - 1]);
        }
        System.out.println(las.solve_optimise());
    }
}

class LAS2 {
    public static final int N = 100010;
    int n;
    int[] a = new int[N];
    int[] q = new int[N];

    public LAS2(int n) {
        this.n = n;
    }

    public int solve_optimise() {
        q[0] = -1 << 30;
        int len = 0;
        for (int i = 1; i <= n; i++) {
            int l = 0, r = len;
            // 找到最大的小于a[i]的数的下标,并将该数后面的一个数赋值为a[i]
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (q[mid] < a[i]) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            // 二分查找中
            // 如果w[i]比q中所有数都大，则r会指向q的最右端，len++(r+1)，并将该数存入q的最后一个位置，保证q单调增
            // 如果w[i]的位置在q中，则r会指向q中最小的比w[i]大的数，len不变，将该位置的值赋值为w[i]，保证q单调增
            len = Math.max(len, r + 1);
            q[r + 1] = a[i];
        }
        return len;
    }
}

/*
8
3 1 2 1 7 8 5 6
 */